package algorithm.sort;

import com.mysql.jdbc.StringUtils;
import org.apache.commons.csv.CSVFormat;
import org.apache.commons.csv.CSVPrinter;

import java.io.*;
import java.net.URLEncoder;
import java.nio.charset.StandardCharsets;
import java.util.List;

public class quickSort {
    public static void quickSort(int[] array, int begin, int end){

        if (end <= begin) {
            return;
        }
        int priot = partition(array,begin,end);
        quickSort(array, begin,priot-1);
        quickSort(array,priot+1,end);
    }

    //分区
    static int partition(int[] array, int begin, int end){
        int count = begin;
        for (int i=begin;i<end;i++) {
            if (array[i] < array[end]) {
               int temp = array[begin];
                array[begin] = array[count];
                array[count] = temp;
                count++;
            }
        }
        int temp = array[count];
        array[count] = array[end];
        array[end] = temp;
        return count;
    }

        // Java
/*    public static void quickSort(int[] array, int begin, int end) {
        if (end <= begin) return;
        int pivot = partition(array, begin, end);
        quickSort(array, begin, pivot - 1);
        quickSort(array, pivot + 1, end);
    }
    static int partition(int[] a, int begin, int end) {
        // pivot: 标杆位置，counter: 小于pivot的元素的个数
        int pivot = end, counter = begin;
        for (int i = begin; i < end; i++) {
            if (a[i] < a[pivot]) {
                int temp = a[counter]; a[counter] = a[i]; a[i] = temp;
                counter++;
            }
        }
        int temp = a[pivot]; a[pivot] = a[counter]; a[counter] = temp;
        return counter;
    }*/

/*        int[] sortArray = {7,6,5,20,15,9,10,8};
        quickSort.quickSort(sortArray,0,7);
        for (int i=0;i<sortArray.length;i++) {
            System.out.println(sortArray[i]);
        }*/








}
